Sprężyny

Limit pamięci: 64 MB

Bajtoś dostał nową kolekcję sprężyn. Każda z nich została wyprodukowana w pewnych wymiarach, a każde jej rozciągnięcie, bądź ściśnięcie, wymaga dość sporego wysiłku.

Aby wydłużyć lub skrócić o centymetr nieruszaną jeszcze sprężynę, potrzeba 1 jednostki wysiłku. Każde kolejne rozciągnięcie, bądź ściśnięcie, tej samej sprężyny wymaga dodatkowo zwiększenia wysiłku o 1. Dokładniej, jeśli Bajtoś chce wydłużyć sprężynę o centymetrów, to będzie się wysilał o kolejno jednostek wysiłku.

Bajtoś zastanawia się, ile minimalnie wysiłku musi włożyć, aby najkrótszych sprężyn było tej samej długości. Zakładamy, że wszystkie sprężyny Bajtosia nie były dotąd rozciągane ani ściskane.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite (), oznaczające odpowiednio liczbę sprężyn oraz liczbę zapytań Bajtosia. Kolejny wiersz zawiera liczb całkowitych (), gdzie oznacza długość -tej sprężyny. Następny wiersz zawiera liczb całkowitych (), gdzie oznacza -te zapytanie Bajtosia, w którym wybiera najmniejszych sprężyn.

Możesz założyć, że w testach wartych łącznie punktów zachodzą dodatkowe warunki i , w testach wartych łącznie punktów zachodzi i , a w testach wartych punktów zachodzi .

Wyjście

-ty wiersz wyjścia powinien być odpowiedzią na -te zapytanie (to jest ile minimalnie wysiłku kosztowałoby Bajtosia ustawienie najkrótszych sprężyn na tą samą długość) modulo .

Przykład

Dla danych wejściowych:

4 4 
1 3 4 10
1 2 3 4

poprawną odpowiedzią jest:

0
2
4
28

Autor zadania: Jacek Tomasiewicz.